百度阿波罗番外篇1：布雷斯悖论 | 厚势汽车

Original 沈纪余厚势汽车 2024-04-13

笔者按：半个月前，我写了一篇早该在去年 4 月 19 日建约车评丢弹的时候就该写的、分析百度 Apollo 计划的文章《为什么说百度阿波罗画虎不成反类犬？》（注：论证更严密的最新版本在笔者的知乎专栏上，有兴趣阅读可点击文末「阅读原文」链接）。没想到这页引起了百度 Apollo 最高层的注意，其公关团队也发了《狗年开工大吉，今天说说是虎还是犬这件事儿》来回应。

百度 Apollo 计划这件事还有很多点可以写，足以构成一个番外篇系列，来详细解释自动驾驶汽车产业的正确打开方式。本文作为番外篇的第 1 篇，想将《为什么说百度阿波罗画虎不成反类犬？》一文中的核心理论依据之一「博弈论」再展开说一下，因为由其导出的结论——「布雷斯悖论」（Braess' Paradox）将对在道路全是自动驾驶汽车上行驶的时代（或许 50 年后会实现）有着非常重要的启示，也会影响整个城市交通体系的设计。

某种程度上，全自动驾驶汽车像极了在互联网上传输的移动数据包。

不论是在交通运输网络中行驶，还是通过互联网传送数据包，都会涉及到博弈论推理：每个人都需要根据自己或他人的选路决策，评估多条路线，并作出最终选择，而不是随便挑选一条路线。

在本文中，我们将利用博弈论的思想构建交通网络流量模型。这个过程中，我们会发现一个非常意外的结果一一布雷斯悖论的观点表明，增加网络容量有时反而会减慢交通网络的流通速度。

1. 纳什均衡态的流量

我们首先构建一个运输网络的模型，观察网络如何应对交通堵塞。在此基础上，进一步引入博弈论的思想来讨论有关问题。

用有向图表示一个运输网络：边表示高速公路，节点表示进入或离开高速路的出入口。假设有两个特别的节点 A 和 B，每个入都要从 A 开车到 B。可以想象，A 是城郊附近的一个出入口，B 是市中心的一个出入口，我们要分析上下班高峰期的车辆行驶情况。最后，根据当前交通量，每条边都有一个特定的行程时间。

图 1 一个高速公路网络

为使这个问题更为具体化，参见图 1。每条边都标记出当有辆车行驶时的行程时间（以分钟计算）。简单举个例子，A-D 和 C-B 边并不受交通状况影响：无论有多少辆车行驶在其中，都需要 45 分钟穿越。相比之下，A-C 和 D-B 边受拥堵的影响较大：当有辆车行驶在同一条路线时，穿越该路线所需要的时间为 100 分钟。．

现在，假设有 4000 辆车希望在早晨上班时能从节点 A 行驶到 B。每一辆车有两种可能的路线：通过 C 的路线或者通过 D 的路线。假设每辆车都选择上面的路线（通过 C)，那么每辆所需用的总时间为 85 分钟，即 4000/100+45 = 85。如果每辆车都选择下面的路线，结果也是一样。然而，如果所有的车被均分到两条路线，每条路线承载 2000 辆车，那么两条路线每辆车所需的时间为 2000/10+45 = 65。

2. 推理过程

我们期待会发生什么呢？以上所描述的流量模型其实就是一场博弈，参与者相当于司机，每个参与者可能的策略是由 A 到 B 的可能路线。这个例子中，每个参与者只有两个策略；而在更大的网络中，每个参与者可选择的策略有很多，每个参与者得到的回报就是他/她行程时间的负数（之所以使用负数是因为较多的行程时间意味着比较糟糕）。

这很自然地与前面构建的框架相吻合。有一点需要注意：在《为什么说百度阿波罗画虎不成反类犬？》一文中，我们用到的例子中，博弈活动只有两个参与者，而这个交通流量模型中涉及很多人（以上例子中大概有 4000 人）。但这并不影响我们应用前面的理论观点。

一个博弈中可以有任何数量的参与者，其中每个人又可有任何数量的策略，每个参与者得到的回报取决于所有参与者所选择的策略。一个纳什均衡是一组策略组合，每个参与者选择其中的一个策略，并且每个选择都是基于其他决策的最好的回应。占优策略、混合策略以及纳什均衡，这些定义都与仅有两个参与者的博弈类似。

在这个流量博弈中，通常是没有占优策略。举例来讲，在图 1 中，每条路线都有可能成为参与者最好的选择，前提是其他参与者会选择另一条路线。这个博弈存在纳什均衡，正如我们将要讨论的，任何一组策略——如果司机能均等地选择两条路线（每条路 2000 辆车），都能够形成纳什均衡，并且这是形成纳什均衡的唯一条件。

为什么车辆在两条路线上等分会产生一个纳什均衡，并且为什么所有的纳什均衡都有这种等分的特性？

要回答第一个问题，我们观察到，当两条路线等分车辆时，没有司机会有动机想要换到另外一条路线。

而第二个问题，考虑一组策略，其中 x 辆车使用上面的路线，剩余的 4000 - x 辆车使用下面的路线。如果 x 不等于 2000，两条路线就会有不同的行驶时间，那么在较慢路线上行驶的司机都会有动机想要换到更快的路线上去。因此，任何 x ≠ 2000 的策略组合都不能形成纳什均衡，而任何 x = 2000 的策略组合都形成一个纳什均衡。

3. 布雷斯悖论

在图 1 中，一切都运作得很好：每个司机自我利益占优的行为造成他们在均衡状态下能在可选的路线中完美地平衡。但是，仅仅对网络做一个小改变，就会形成一个有悖常理的状态。

图 2 在图 1 中增加一个从 C 到 D 的高速路线

我们做如下改变：假设市政府计划从 C 到 D 新建一条高速公路，如图 2 所示。为了使事情简单化，设它的行程时间为 0，不管有多少辆车在此路线上都一样，尽管由此产生的效果有别于实际情况（但影响应该很少）。按常理推断 C 到 D 的路建成后，A 到 B 的运行时间会减少很多。

实际结果令人吃惊：在这个新的高速网络中存在一个唯一的纳什均衡，但是它导致大家花费更多的行驶时间。在纳什均衡状态下，每个司机都使用从 C 到 D 的路线，结果每个司机需要的行驶时间为80（4000/100+0+4000/100 = 80）分钟。

进一步分析为什么这是一个均衡，注意到此时没有司机能从改变路线中受益：有了从 C 到 D 的路线后，其他任何一条路线都需花费 85 分钟。那么为什么说这是唯一的均衡？可以看到，从 C 到 D 路线的建立事实上使此路线成为所有司机的占优策略：不管当前的流量模式是什么，换到从 C 到 D 的路线都会受益。

换句话说，一旦由 C 到 D 的高速路建成，此路线就像一个漩涡，将所有司机都吸引至此，这对所有人都有害。在新的网络中，如果所有司机的行为都是自我利益占优，就没有办法使网络恢复到一个对大家都更好的等分情况。

这种现象，即一个运输网络增加新的资源有时反而使均衡状态中的性能受损，最早由德国 Ruhr-Universität Bochum 的数学家 Dietrich Braess 在 1968 年就已提出，随后被称为布雷斯悖论（Braess' Paradox）。就像很多有悖常理的异常现象一样，它们的出现是基于实际生活中各种条件的恰当结合。在实际的运输网络中也曾经被观察到，韩国首尔市曾拆毁一条有 6 条行车道的高速路而改建成一个公园，实际上反而减少了出入该城市的交通时间（尽管交通量跟改建之前大致相似）。

4. 布雷斯斯悖论的启示

通过上文的描述，我们了解到了布雷斯悖论的影响方式（值得注意的是它本身并没有自相矛盾），则可以认为，在很多设置环境中，给一个博弈增加一个新策略会使情况变得更糟。

比如，在《为什么说百度阿波罗画虎不成反类犬？》一文中所用到的例子「囚徒困境」中：假如对每个囚徒来说，他们唯一的策略是「不认罪」(一个非常简单的博弈），那么对双方来说，其结果要好于加入「认罪」这项选择（这就是为什么警方会首先提供「认罪」这个选择）。

然而直观上，基于布雷斯悖论的类似现象又似乎是自相矛盾。我们都会有一个非正式的感知，认为升级一个网络一定是件好事情，所以当结果使其变糟时，都会感到惊讶。

因此，笔者认为，在未来道路上全部是 SAE Level 5 的自动驾驶汽车时，还是需要某些中央控制系统，对道路上的整体交通流量进行主动调节，而不是任由事态向糟糕的纳什均衡态演变。如上文针对布雷斯悖论所论述的，这种纳什均衡的收益并不是最优的！

当然，百度阿波罗也可以通过剔除掉「测试数据作弊」这一选项/策略，来实现所谓的降低自动驾驶汽车的研发门槛（其实 Apollo 的开源代码只足以开发一款「玩具车」），只是不知道百度的高层想不想得出这个办法。

事实上，学术界对此早已有研究。

参考文献

1. Benedict Evans. Cars and Second Order Consequences. A16Z. 2017.03.29

2. David Easley, Jon Kleinberg. Network, Crowds, and Markets: Reasoning about a Highly Connected World [M]. Cambridge University Press. 2010

编辑整理：厚势首席分析师沈纪余

转载请注明来自厚势和厚势公号：iHoushi